#include "BinarySearchTree.h"
#include <vector>
#include <random>
#include <ctime>

template<typename Comparable> 
void Randomized_BST_sort(std::vector<Comparable> &data);
template<typename Comparable>
void BST_sort(std::vector<Comparable> &data);


int main(){
    int n;
    int m;
    int ty;

    std::cout<<"请输入测试BST_sort函数的向量长度："<<endl;
    std::cin>>n;
    std::cout<<"请输入测试Randomized_BST_sort函数的向量长度："<<endl;
    std::cin>>m;
    std::cout<<"请输入测试向量生成的方式（1为升序，0为降序）："<<endl;
    std::cin>>ty;

    clock_t start, end;

    int time = 0;

    start=clock();
    std::vector<int> b(n);
    if(ty==0){
    for(int i=0;i<n;i++)
    b[i]=2*n-i;
    Randomized_BST_sort(b);
    std::cout<<"sort 函数输出结果为："<<endl;
    for(int i=0;i<b.size();i++)
    {

        std::cout<<b[i]<<" ";
    }
    std::cout<<"\n";
    }
    else{
            for(int i=0;i<n;i++)
    b[i]=i;
    Randomized_BST_sort(b);
    std::cout<<"sort 函数输出结果为："<<endl;
    for(int i=0;i<b.size();i++)
    {

        std::cout<<b[i]<<" ";
    }
    std::cout<<"\n";
    }


    end = clock();
        time = end - start;
    std::cout << "sort函数用时为： " << time << "  单位时间\n"
            << std::endl;


    start=clock();
    std::vector<int> c(m);

    if(ty==0)
    {for(int i=0;i<m;i++)
    c[i]=2*m-i;
    Randomized_BST_sort(c);
    std::cout<<"Randomized sort 函数输出结果为："<<endl;
    for(int i=0;i<c.size();i++)
    {

        std::cout<<c[i]<<" ";
    }
    std::cout<<"\n";}
    else{
        for(int i=0;i<m;i++)
    c[i]=i;
    Randomized_BST_sort(c);
    std::cout<<"Randomized sort 函数输出结果为："<<endl;
    for(int i=0;i<c.size();i++)
    {

        std::cout<<c[i]<<" ";
    }
    std::cout<<"\n";
    }
    end = clock();
        time = end - start;
    std::cout << "Randomized sort函数用时为： " << time << "  单位时间\n"
            << std::endl;

}
/*
其中order函数在BST类内实现
    void order(vector<Comparable>* data, BinaryNode* node)
    {
        if (node==nullptr)
        return;
        else
        {
            order(data, node->left);
           (*data).push_back(node->element);
    
            order(data, node->right);
            
        }

    }
*/
template<typename Comparable>
void BST_sort(std::vector<Comparable> &data)
{
    BinarySearchTree<Comparable> A;
    vector<Comparable>* p;
    int sum=data.size();
    for(int i=0;i<data.size();i++)
    {
        A.insert(data[i]);
    }
    p=&data;
    data.clear();
    A.order(p,A.root);

}


template<typename Comparable> 
void Randomized_BST_sort(std::vector<Comparable> &data)
{
    int n=data.size();
    for(int i=1;i<n;i++)
    {
        int a=rand() % n;
        int b=rand() % n;
        Comparable digit;
        digit = data[b];
        data[b]=data[a];
        data[a]=digit;
    }
    BST_sort(data);
}


